#include <limits.h>  // INT_MIN,INT_MAX
#include <math.h>    // abs,pow

#include <algorithm>      // sort
#include <iostream>       // cout,cin
#include <numeric>        // accumulate
#include <string>         // string
#include <unordered_map>  // unordered_map
#include <unordered_set>  // unordered_set
#include <vector>         // vector

using namespace std;

// 链表结点的数据结构
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

// 如果x是2的幂则返回True，否则返回False
bool IsPowerOf2(int x) { return (x & (x - 1)) == 0; }

class LRUCache {
   private:
    // 双向链表数据结构
    struct Node {
        int key, val;
        Node *left, *right;

        Node(int k, int v) : key(k), val(v), left(nullptr), right(nullptr) {}
    };

    // 删除双向链表的结点p
    void remove(Node* p) {
        p->left->right = p->right;
        p->right->left = p->left;
        p->left = nullptr;
        p->right = nullptr;
    }

    // 在双向链表的开头添加结点p
    void insert(Node* p) {
        p->left = L;
        p->right = L->right;
        L->right->left = p;
        L->right = p;
    }

    unordered_map<int, Node*> hash;
    int free;
    Node *L, *R;

    // 将当前使用的节点移动的双向链表的开头
    void activate(Node* p) {
        remove(p);
        insert(p);
    }

    // 将当前双向链表的即为移除
    void pop() {
        Node* p = R->left;
        hash.erase(p->key);
        remove(p);
    }

   public:
    LRUCache(int capacity) {
        free = capacity;
        L = new Node(-1, -1);  // 左侧哨兵结点
        R = new Node(-1, -1);  // 右侧哨兵结点
        L->right = R;
        R->left = L;
    }

    int get(int key) {
        if (hash.count(key)) {
            Node* node = hash[key];
            activate(node);
            return node->val;
        } else {
            return -1;
        }
    }

    void put(int key, int value) {
        if (hash.count(key)) {
            Node* node = hash[key];
            node->val = value;
            activate(node);
        } else {
            Node* node = new Node(key, value);
            hash[key] = node;
            insert(node);
            if (free == 0) {
                pop();
            } else {
                free--;
            }
        }
    }
};

int main() { return 0; }